package main.Q1_100;

import java.util.*;

public class Q11_20 {
    public static void main(String[] args) {
        System.out.println("Question11：盛最多水的容器");
        System.out.println("Question12：整数转罗马数字");
        System.out.println("Question13：罗马数字转整数");
        System.out.println("Question14：最长公共前缀");
        System.out.println("Question15：三数之和");
        System.out.println("Question16：最接近的三数之和");
        System.out.println("Question17：电话号码的字母组合");
        System.out.println("Question18：");
        System.out.println("Question19：删除链表的倒数第N个节点");
        System.out.println("Question20：有效的括号");
    }
}

class Question11{
    public int maxArea(int[] height) {//双指针
        int left=0,right= height.length-1,maxArea=0;
        while (left<right){
            int area=Math.min(height[left],height[right])*(right-left);
            maxArea=Math.max(maxArea,area);
            if (height[left]<=height[right]) left++;
            else right--;
        }
        return maxArea;
    }
}

class Question12{
    public String intToRoman(int num) {
        String[] thousands = {"", "M", "MM", "MMM"};
        String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }
}

class Question13{
    public int romanToInt(String s) {
        int result=0;
        for (int i=0;i<s.length();i++){
            char temp=s.charAt(i);
            switch (temp){
                case 'I':
                    if ((i<s.length()-1)&&(s.charAt(i + 1) == 'V' || s.charAt(i + 1) == 'X'))  result = result - 1;
                    else result = result + 1;
                    break;
                case 'V':result=result+5;break;
                case 'X':
                    if ((i<s.length()-1)&&(s.charAt(i + 1) == 'L' || s.charAt(i + 1) == 'C')) result = result - 10;
                    else result=result+10;
                    break;
                case 'L':result=result+50;break;
                case 'C':
                    if ((i<s.length()-1)&&(s.charAt(i + 1) == 'D' || s.charAt(i + 1) == 'M')) result = result - 100;
                    else result=result+100;
                    break;
                case 'D':result=result+500;break;
                case 'M':result=result+1000;break;
                default:break;
            }
        }
        return result;
    }
}

class Question14{
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

class Question15{
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) return result;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) right--;
                else if (sum < 0) left++;
                else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

class Question16{
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - result))
                    result = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return result;
            }
        }
        return result;
    }
}

class Question17{
    List<String> list=new ArrayList<>();
    char[][] table={{},{},{'a','b','c'},{'d','e','f'},
            {'g','h','i'},{'j','k','l'},{'m','n','o'},
            {'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
    public void process(char[] str,int start,StringBuffer lastStr){
        if (start==str.length){//数字用完
            String curStr=new String(lastStr);
            list.add(curStr);
            return;
        }
        char[] temp=table[str[start]-48];
        StringBuffer curStr=new StringBuffer(lastStr);
        for (int i=0;i<temp.length;i++){
            curStr.append(temp[i]);//本次添加
            process(str,start+1,curStr);//后续添加
            curStr.deleteCharAt(curStr.length()-1);//撤销本次添加
        }
    }
    public List<String> letterCombinations(String digits) {
        char[] str=digits.toCharArray();
        if (str.length>0) {
            StringBuffer s = new StringBuffer();
            process(str, 0, s);
        }
        return list;
    }
}

class Question19{
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode virtual=new ListNode();
        virtual.next=head;
        ListNode p1=virtual,p2=head;
        for (int i=0;i<n;i++) p2=p2.next;
        while (p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return virtual.next;
    }
}

class Question20{
    public boolean isValid(String s) {
        if (s.length()==0) return true;
        char[] str=s.toCharArray();
        Stack<Character> stack=new Stack<>();
        for (int i=0;i< str.length;i++){
            if (!stack.isEmpty()) {//栈不为空
                char top = stack.peek();//栈顶元素
                if (top == '(' && str[i] == ')') stack.pop();
                else if (top == '[' && str[i] == ']') stack.pop();
                else if (top == '{' && str[i] == '}') stack.pop();
                else stack.add(str[i]);//均未匹配，则入栈
            }else stack.add(str[i]);
        }
        if (stack.isEmpty()) return true;
        else return false;
    }
}